package leetcode;

import java.security.Key;
import java.util.*;

public class LeetCode89 {

    public static void main(String[] args) {
        LeetCode89 leetCode89 = new LeetCode89();
        leetCode89.judgeGeLei(1, 3);
    }

    List<Integer> result;

//    Map<Integer, Integer> dict = new HashMap<>();

    public List<Integer> grayCode(int n) {
        int[] used = new int[(int) Math.pow(2, n)];
        helper(used, new ArrayList<>());
        return result;
    }

    private void helper(int[] used, List<Integer> list) {
        if (result != null)
            return;
        if (used.length == list.size())
            result = list;
        else {
            int n = used.length;
            for (int i = 0; i < n; i++) {
                if (used[i] == 0 && (list.size() == 0 || judgeGeLei(list.get(list.size() - 1), i))) {
                    used[i] = 1;
                    List<Integer> tmp = new ArrayList<>(list);
                    tmp.add(i);
                    helper(used, tmp);
                    used[i] = 0;
                }
            }
        }
    }

    private boolean judgeGeLei(int x, int y) {
        int count = 0;
        String s1 = Integer.toBinaryString(x);
        String s2 = Integer.toBinaryString(y);
        int n1 = s1.length();
        int n2 = s2.length();
        if (n1 > n2) {
            StringBuffer sb = new StringBuffer();
            for (int i = n2; i < n1; i++) {
                sb.append(0);
            }
            s2 = sb.append(s2).toString();
        } else {
            StringBuffer sb = new StringBuffer();
            for (int i = n1; i < n2; i++) {
                sb.append(0);
            }
            s1 = sb.append(s1).toString();
        }
        int i = 0, n = s1.length();
        while (i < n) {
            if (s1.charAt(i) != s2.charAt(i))
                count++;
            i++;
        }
        return count <= 1;
    }

    public List<Integer> grayCode1(int n) {
        Map<Integer, LinkedList<Integer>> dict = new HashMap<>();
        Map<Integer, Integer> countDict = new HashMap<>();
        for (int i = 0; i < n; i++) {
            String s = Integer.toBinaryString(i);
            int count = 0;
            for (char c : s.toCharArray()) {
                if (c == '1')
                    count++;
            }
            if (dict.containsKey(count)) {
                dict.get(count).add(i);
            } else {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                dict.put(count, list);
            }
            countDict.put(count, countDict.getOrDefault(count, 0) + 1);
        }
        System.out.println(dict);
        System.out.println(countDict);
        return null;
    }
//------------------------------------------------------------------
}
